#include "DynamicArray.h"
#include <stdio.h>
#include <stdlib.h>

struct  DynamicArray;//前置声明

struct DynamicArray
{
    ElementType *array;
    int capacity;   //数组容量
    int size;   //数组大小

};

DArray * InitDArray(int capacity)
{
    DArray *a = (DArray*)malloc(sizeof(DArray));
    if (a == NULL)
    {
        printf ("申请DArray失败\n");
        return NULL;
    }
    //初始化结构体变量
    a->capacity = capacity;
    a->size = 0;
    a->array =(ElementType) malloc (sizeof(ElementType) * a->capacity);
    if (a->array == NULL)
    {
        printf ("申请数组失败!\n");
        free(a);
        return NULL;
    }
    return a;
}


bool InsertTail (DArray * a,ElementType element)
{
    //数组放满了
    if (a->size >= a->capacity)
    {
        ElementType *newP = (ElementType*)malloc(sizeof (ElementType) *a->capacity * 2);
        if (newP == NULL)
        {
            printf ("扩容失败\n");
            return false;
        }
            for (int i=0;i<a->size ;i++)
            {
                newP[i] = a->array[i];
            }
        free(a->array);
        a->array - newP;
        a->capacity *=2;
        }
    a->array[a->size++] = element;
    return true;
}


//释放动态数组
void FreeDArray(DArray *a )
{
    if (a)
    {
        //数组指针不为空
        if (a ->array)
        {
            free(a ->array);
        }
        free (a);
    }
}

//打印数组
void PrintArray(DArray * a)
{
    for (int i=0;i<a->size;i++)
    {
        printf ("%d ",a->array[i]);
    }
    printf ("\n");
}

//按照位置删除数组
void RemoveByIndex(DArray *a,int index)
{
    if (index < 0||  index > a->size )
    {
        printf ("非法的位置");
        return ;
    }

    for (int i=index; i<a->size-1;i++)
    {
        a->array[i] = a->array[i+1];//把数组中所有位置往前移
    }
    a->size --;
}

//按照值删除数组
void RemoveByElement(DArray *a, ElementType element)
{
    for (int i=0; i< a->size;i++)
    {
        if (a->array[i]== element)
        {
            RemoveByIndex(a,i);
            i--;
        }
    }
}



ElementType FindByElement(DArry* a),ElementType elemtent,bool (*find)(ElementType));
{
    for (int i=0;i<a->size;i++)
    {
        if (find(a->array[i],element)==true)
    {
        return a->array[y];
    }
    return NULL;
    }
}

void FastSort(ElementType *a, int start, int end)
{
    if(start >= end)
    return;

    int left = start;
    int right = end;
    int temp = a[left];

    while(left < right)
    {
        //先从右边动 找比基准值小的数
        while(SortPtr(a[right,temp]) ==true  && left < right)
        {
            right--;
        }
        //把右边的值赋给左边的空位
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }
        //左边动 找比基准值大的数
        while(SortPtr(temp,a[left]) == true  && left < right)
        left++;

        //把左边的值赋给右边的空位
        if(left < right)
        a[right--] = a[left];
    }
    //基准值给到这个位置
    a[left] = temp;

    //递归排序
    FastSort(a,start,left-1,SortPtr);
    FastSort(a,right+1,end,SortPtr);
}



void DArrayFastSort(DArray * a, bool(* SortPtr)(ElementType,ElementType))
{
    FastSort(a->array,0,a->size,SortPtr);
}